//Find all valid combinations of k numbers that sum up to n such that the follow
//ing conditions are true: 
//
// 
// Only numbers 1 through 9 are used. 
// Each number is used at most once. 
// 
//
// Return a list of all possible valid combinations. The list must not contain t
//he same combination twice, and the combinations may be returned in any order. 
//
// 
// Example 1: 
//
// 
//Input: k = 3, n = 7
//Output: [[1,2,4]]
//Explanation:
//1 + 2 + 4 = 7
//There are no other valid combinations. 
//
// Example 2: 
//
// 
//Input: k = 3, n = 9
//Output: [[1,2,6],[1,3,5],[2,3,4]]
//Explanation:
//1 + 2 + 6 = 9
//1 + 3 + 5 = 9
//2 + 3 + 4 = 9
//There are no other valid combinations.
// 
//
// Example 3: 
//
// 
//Input: k = 4, n = 1
//Output: []
//Explanation: There are no valid combinations.
//Using 4 different numbers in the range [1,9], the smallest sum we can get is 1
//+2+3+4 = 10 and since 10 > 1, there are no valid combination.
// 
//
// Example 4: 
//
// 
//Input: k = 3, n = 2
//Output: []
//Explanation: There are no valid combinations.
// 
//
// Example 5: 
//
// 
//Input: k = 9, n = 45
//Output: [[1,2,3,4,5,6,7,8,9]]
//Explanation:
//1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45
//There are no other valid combinations.
// 
//
// 
// Constraints: 
//
// 
// 2 <= k <= 9 
// 1 <= n <= 60 
// 
// Related Topics 数组 回溯 
// 👍 356 👎 0


package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

//Java：Combination Sum III
class P216CombinationSumIii {
    public static void main(String[] args) {
        Solution solution = new P216CombinationSumIii().new Solution();
        // TO TEST
        System.out.println(solution.combinationSum3(3, 10));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        boolean[] visited = new boolean[9];
        List<List<Integer>> res = new ArrayList<>();

        public List<List<Integer>> combinationSum3(int k, int n) {
            combinationSum3(k, n, 0, new ArrayList<>(), 1);
            return res;
        }

        private void combinationSum3(int k, int n, int depth, List<Integer> list, int start) {
            if (depth == k) {
                if (n == 0) {
                    res.add(new ArrayList<>(list));
                }
                return;
            }
            for (int i = start; i <= 9; i++) {
                if (visited[i - 1]) {
                    continue;
                } else {
                    visited[i - 1] = true;
                    list.add(i);
                    combinationSum3(k, n - i, depth + 1, list, i + 1);
                    list.remove(list.size() - 1);
                    visited[i - 1] = false;
                }
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}